# coding=utf-8
from collections import deque

from python.unit6_tree.part1_basic.Tree import Tree


#  验证是否为有效搜索树
class IsValidBST:
    # 迭代实现
    def isValidBST(self, root):
        stack, inorder = [], float('-inf')
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if root.val <= inorder:
                return False
            inorder = root.val
            root = root.right

        return True

    # 递归实现
    def isValidBST2(self, root):
        def helper(node, lower=float('-inf'), upper=float('inf')):
            if not node:
                return True

            val = node.val
            if val <= lower or val >= upper:
                return False

            if not helper(node.right, val, upper):
                return False
            if not helper(node.left, lower, val):
                return False
            return True


if __name__ == "__main__":
    tree = Tree()
    root = tree.init_tree_for_valid_bst()
    isValidBST = IsValidBST()
    res = isValidBST.isValidBST2(root)
    print res
